<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:
                示例 1：

                输入：nums = [1,2,3], target = 4
                输出：7
                解释：
                所有可能的组合为：
                (1, 1, 1, 1)
                (1, 1, 2)
                (1, 2, 1)
                (1, 3)
                (2, 1, 1)
                (2, 2)
                (3, 1)
                请注意，顺序不同的序列被视作不同的组合。
                示例 2：

                输入：nums = [9], target = 3
                输出：0
        */


        /*
            动态规划解法:
                这个解法非常不利于理解
        */
        var combinationSum4 = function(nums, target) {
            let dp = new Array(target + 1).fill(0).map(item => new Array(nums.length + 1).fill(0))

            // 初始化第0行
            for (let j = 1; j <= nums.length; j++) {
                dp[0][j] = 1
            }
            // 外层遍历背包（目标和）
            for (let i = 1; i <= target; i++) {
                // 内层遍历nums数组的元素
                for (let j = 1; j <= nums.length; j++) {
                    // 如果当前目标和j大于等于nums[i]，可以考虑使用nums[i]
                    if (nums[j - 1] <= i) {
                        for (let k = 0; k < j; k++) {
                            if (i - nums[k] > -1) {
                                dp[i][j] = dp[i][j] + dp[i - nums[k]][j]
                            }
                        }
                    } else {
                        // 如果j小于nums[i]，只能延续前一个状态
                        dp[i][j]= dp[i][j-1]
                    }
                }
            }

            // 返回最终结果
            return dp[target][nums.length];
        };
        console.log(combinationSum4([1, 2, 3], 4));
    </script>
</body>

</html>